package com.dhu.graph.basic.paths.impls;

import com.dhu.graph.basic.GraphImpls.Graph;
import com.dhu.graph.basic.paths.Paths;
import com.dhu.graph.utils.ArrayQueue;

import java.util.Stack;


/**
 * 广度优先搜索
 */
public class BreadFirstPaths implements Paths {
    private final int s;// 图的起点
    private boolean[] marked;   //到达该定点的最短路径是否已知
    private int[] edgTo;    //到达该定点的前一个顶点

    public BreadFirstPaths(Graph G, int s){
        this.s = s;
        this.marked = new boolean[G.getVertexes()];
        this.edgTo = new int[G.getVertexes()];
        bsf(G,s);
    }

    private void bsf(Graph G, int s){
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        marked[s] = true;
        queue.enqueue(s);
        while(!queue.isEmpty()){
            int v = queue.dequeue();
            for(int w: G.adj(v)){
                if(!isMarked(w)){
                    edgTo[w] = v;
                    marked[w] = true;
                    queue.enqueue(w);//将与v相邻的顶点入队
                }
            }
        }
    }

    private boolean isMarked(int v){
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathsTo(int v) {
        Stack<Integer> stack = new Stack<>();
        for (int w = v; w != s; w = edgTo[w]){
            stack.push(w);
        }
        stack.push(v);
        return stack;
    }

    @Override
    public boolean hasPathTo(Integer v) {
        return marked[v];
    }
}
